package uestc.lj.advanced.dp;

/**
 * @Author:Crazlee
 * @Date:2021/12/9
 */
public class Code01_MoneyWays {
	/**
	 * 用任意枚普通币和最多一枚纪念币拼money，做多的拼法
	 *
	 * @param arbitrary 普通币面值
	 * @param onlyone   纪念币面值
	 * @param money     总钱数
	 * @return 最多的拼接方法
	 */
	public static int moneyWays(int[] arbitrary, int[] onlyone, int money) {
		if (money < 0) {
			return 0;
		}
		if ((arbitrary == null || arbitrary.length == 0) &&
				(onlyone == null || onlyone.length == 0)) {
			return money == 0 ? 1 : 0;
		}
		int[][] dparb = getDpArb(arbitrary, money);
		int[][] dpone = getDpOne(onlyone, money);
		if (dparb == null) {
			return dpone[dpone.length - 1][money];
		}
		if (dpone == null) {
			return dparb[dparb.length - 1][money];
		}
		int res = 0;
		for (int i = 0; i <= money; i++) {
			res += dparb[dparb.length - 1][i]
					* dpone[dpone.length - 1][money - i];
		}
		return res;
	}

	private static int[][] getDpOne(int[] onlyone, int money) {

		if (onlyone == null || onlyone.length == 0) {
			return null;
		}
		int[][] dp = new int[onlyone.length][money + 1];
		for (int i = 0; i < onlyone.length; i++) {
			dp[i][0] = 1;
		}
		if (onlyone[0] <= money) {
			dp[0][onlyone[0]] = 1;
		}
		for (int i = 1; i < onlyone.length; i++) {
			for (int j = 1; j <= money; j++) {
				dp[i][j] = dp[i - 1][j];
				dp[i][j] += j - onlyone[i] >= 0 ? dp[i - 1][j - onlyone[i]] : 0;
			}
		}
		return dp;
	}

	private static int[][] getDpArb(int[] arbitrary, int money) {
		if (arbitrary == null || arbitrary.length == 0) {
			return null;
		}
		//0...i范围上搞定money有多少种方法
		int[][] dp = new int[arbitrary.length][money + 1];
		// 第一列上表示0...i范围上搞定0块钱有多少种方法
		for (int i = 0; i < arbitrary.length; i++) {
			dp[i][0] = 1;
		}
		// 第一行上表示搞定arbitrary[0]的倍数钱有多少种方法
		for (int j = 1; arbitrary[0] * j <= money; j++) {
			dp[0][arbitrary[0] * j] = 1;
		}
		for (int i = 1; i < arbitrary.length; i++) {
			for (int j = 1; j <= money; j++) {
				// 不用arbitrary[i]的货币和用k张
				dp[i][j] = dp[i - 1][j];
				dp[i][j] += j - arbitrary[i] >= 0 ? dp[i][j - arbitrary[i]] : 0;
			}
		}
		return dp;
	}
}
